One challenge in games is determining how to handle autonomous navigation and planning of many agents (i.e. non-player characters) in a scene with both static and dynamic moving obstacles. In a real-time game, agents must find their route to a particular goal position avoiding collisions with obstacles or other agents in the environment. The computational complexity of simulating multiple agents in a crowded scene becomes intractable and arises from the fact that each moving agent is a dynamic obstacle to other agents.
Ideally, each agent would navigate independently without implying any global coordination or synchronization of all or a subset of the agents involved. This is analogous to the way individual humans navigate in a shared environment, where each person makes independent observations and decisions without explicit communication with others.
Navigational planning techniques for multi-agent environments have been traditionally studied in the domain of robotics and in recent years have been increasingly applied to games. Centralized techniques consider the sum of all agents to be a single agent and a solution is searched in a composite space. However, as the number of agents increases, problem complexity becomes prohibitively high. Decoupled planners, on the contrary, are more distributed but require coordination space that may not always guarantee completeness.
A real-time motion planning technique using per-particle energy minimization and adopting a continuum perspective of the environment is one technique that has been implemented. This formulation yields a set of dynamic potential and velocity fields over a domain that guide all individual motion simultaneously. This approach unifies global path planning and local collision avoidance into a single optimization framework.
Using this technique, the global planning assumption produces significantly smoother and more realistic crowd motion. Nonetheless, in avoiding agent based dynamics altogether the ability to succinctly express the computation in parallel becomes fairly constraint. There is thus a need for addressing these and/or other issues associated with the prior art.